package leetcode.lt100;

class Solution_45 {

	public static void main(String[] args) {
		int[] nums = { 1, 1, 1, 1 };
		int res = new Solution_45().jump(nums);
		System.out.println(res);
	}

	public int jump(int[] nums) {
		int res = 0;
		// 从头开始遍历
		int l = nums.length;
		if (l < 2)
			return 0;

		int max = 0;
		int maxIndex = 0;
		for (int i = 0; i < l;) {
			if (nums[i] + 1 >= l - i) {
				return ++res;
			}
			for (int j = 1; j < nums[i] + 1; j++) {
				if (nums[i + j] + j >= max) {
					max = nums[i + j] + j;
					maxIndex = i + j;
				}
			}
			i = maxIndex;
			res++;
			max = 0;
		}
		return 0;
	}
}